/*
 * @lc app=leetcode.cn id=1005 lang=typescript
 *
 * [1005] K 次取反后最大化的数组和
 */

// @lc code=start

class MinPQ {
  public heap: number[];
  private N: number;

  constructor(maxN: number) {
    this.heap = new Array(maxN + 1);
    this.N = 0;
  }

  public insert(value: number) {
    this.N++;
    this.heap[this.N] = value;
    this.swim(this.N);
  }

  public delMin() {
    const min = this.heap[1];
    this.exch(1, this.N--);
    this.sink(1);
    this.heap[this.N + 1] = null;
    return min;
  }

  private swim(k: number) {
    while (k > 1 && this.less(k, (k / 2) >> 0)) {
      this.exch(k, (k / 2) >> 0);
      k = (k / 2) >> 0;
    }
  }

  private sink(k: number) {
    while (2 * k <= this.N) {
      let j = 2 * k;
      if (j < this.N && this.less(j + 1, j)) j++;
      if (!this.less(j, k)) break;
      this.exch(k, j);
      k = j;
    }
  }

  private less(i: number, j: number) {
    return this.heap[i] < this.heap[j];
  }

  private exch(i: number, j: number) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }
}

function largestSumAfterKNegations(nums: number[], k: number): number {
  // 小顶堆
  const minpq = new MinPQ(nums.length);
  const n = nums.length;
  // 元素入堆
  for (let i = 0; i < n; i++) {
    minpq.insert(nums[i]);
  }
  // 取k次反转
  // 每次取最小元素反转
  for (let i = 0; i < k; i++) {
    const min = minpq.delMin();
    minpq.insert(-min);
  }
  // 累加数组结果
  return minpq.heap.reduce((a, b) => a + b, 0);
}
// @lc code=end
